776D - The Door Problem - CodeForces Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define MOD 1000000007
#define mod(x, m) (((x % m) + m) % m)
#define mxn 200005
#define mxm 100005
#define f first
#define s second
#define pb push_back
#define es " "
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> pip;
 
int n, m, v[mxn], viz[mxn][2], memo[mxn], comp[mxn];
vector<int> vec[mxn], vec2[mxn], st;

void dfs(int x){
    memo[x]=1;
    for(int i:vec[x]){
        if(!memo[i]) dfs(i);
    }
    st.pb(x);
}
void dfs2(int x, int c){
    comp[x]=c;
    for(int i:vec2[x]){
        if(!comp[i]) dfs2(i, c);
    }
}

void add(int x, int sx, int y, int sy){
    vec[x+m*sx].pb(y+m*(!sy));
    vec[y+m*sy].pb(x+m*(!sx));

    vec2[y+m*(!sy)].pb(x+m*sx);
    vec2[x+m*(!sx)].pb(y+m*sy);
}

int main(){
    fastio;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> v[i];
    }
    for(int i=1; i<=m; i++){
        int k;
        cin >> k;
        for(int j=0; j<k; j++){
            int x;
            cin >> x;
            if(!viz[x][0]) viz[x][0]=i;
            else viz[x][1]=i;
        }
    }
    for(int i=1; i<=n; i++){
        if(v[i]){
            add(viz[i][0], 1, viz[i][1], 0);
            add(viz[i][0], 0, viz[i][1], 1);
        }else{
            add(viz[i][0], 1, viz[i][1], 1);
            add(viz[i][0], 0, viz[i][1], 0);
        }
    }
    for(int i=1; i<=2*m; i++){
        if(!memo[i]) dfs(i);
    }
    int cont=0;
    for(int i=2*m-1; i>=0; i--){
        if(!comp[st[i]]){
            dfs2(st[i], ++cont);
        }
    }
    
    for(int i=1; i<=m; i++){
        if(comp[i]==comp[i+m]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}